JZ30 连续子数组的最大和

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

import java.lang.Math;

public class Solution {
    public  int FindGreatestSumOfSubArray(int[] array) {
            int res = array[0]; //记录当前所有子数组的和的最大值
            int max = array[0];   //包含array[i]的连续数组最大值
            for (int i = 1; i < array.length; i++) {
// 核心问题，为什么这里 max(array[i] + dp[i-1], array[i]), 是和 array[i] 做比较？
// 因为题目要求连续子向量（设为X）的和的最大值，如果dp[i-1]+array[i]<array[i]，
// 那么之前计算dp[i-1]的子向量肯定不是所求X的开头段，因为array[i]已经更大了，它才有可能是X的开头段。
                max = Math.max(max + array[i], array[i]); // 因为只有 max 为负时 max + array[i] 才能小于 array[i]
                res = Math.max(max, res);
            }
            return res;
    }
}

对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。